import java.util.*;

public class TranspositionPuzzle implements State, StateWithCost {
	private String state;
	
	/**
	 * Initializes a new <code>TranspositionPuzzle</code> object representing
	 * a string of letters.
	 * 
	 * @param state A string of letters.
	 * @throws IllegalArugmentException If the specified string is
	 * <code>null</code>.
	 */
	public TranspositionPuzzle(String state) {
		if (state == null)
			throw new IllegalArgumentException();
		
		this.state = state;
	}
	
	/**
	 * Modifies this <code>TranspositionPuzzle</code> to represent a random
	 * arrangement of this <code>TranspositionPuzzle</code>'s letters.
	 */
	public void randomize() {
		ArrayList<Character> chars = new ArrayList<>(state.length());
		for (int i = 0; i < state.length(); i++)
			chars.add(state.charAt(i));
		Collections.shuffle(chars);
		StringBuffer sb = new StringBuffer();
		for (Character c : chars)
			sb.append(c);
		state = sb.toString();
	}
	
	/**
	 * Returns a collection of all possible <code>TranspositionPuzzle</code>
	 * configurations reachable by swapping two letters in this
	 * <code>TranspositionPuzzle</code>.
	 * 
	 * @return a collection of all adjacent <code>TranspositionPuzzle</code>
	 * configurations.
	 */
	public Collection<State> getNeighbors() {
		ArrayList<State> neighbors = new ArrayList<>();
		
		for (int i = 0; i < state.length(); i++)			
			for (int j = i + 1; j < state.length(); j++)
				neighbors.add(swap(i, j));
		
		return neighbors;
	}

	/**
	 * Returns a collection of all possible <code>TranspositionPuzzle</code>
	 * configurations reachable by swapping two letters in this
	 * <code>TranspositionPuzzle</code>.  Each adjacent <code>TranspositionPuzzle</code>
	 * is associated with the step-cost of swapping the two letters, where the
	 * step-cost is the distance between the positions of the swapped letters (a positive
	 * integer). 
	 * 
	 * @return a collection of all <code>TranspositionPuzzle</code>s adjacent to this
	 * <code>TranspositionPuzzle</code> and their associated step-costs.
	 */
	public Map<StateWithCost,Double> getNeighborsWithCost() {
		Map<StateWithCost,Double> neighbors = new HashMap<>();
		for (int i = 0; i < state.length(); i++)
			for (int j = i + 1; j < state.length(); j++)
				neighbors.put(swap(i, j), new Double(j - i));
		return neighbors;
	}

	/**
	 * Returns a string representation of this <code>TranspositionPuzzle</code>.
	 * 
	 * @return A string representation of this <code>TranspositionPuzzle</code>.
	 */
	public String toString() {
		return state.toString();
	}

	/**
	 * Indicates whether this <code>TranspositionPuzzle</code> object is equal to
	 * another object.  A <code>TranspositionPuzzle</code> object is equal to another
	 * object if and only if that object is a <code>TranspositionPuzzle</code> 
	 * containing the same letters in the same configuration.
	 * 
	 * @param obj The object with which to compare this
	 * <code>TranspositionPuzzle</code> object. 
	 * @return <code>true</code> if this <code>TranspositionPuzzle</code> is equal to
	 * the specified object, or <code>false</code> otherwise. 
	 */
	public boolean equals(Object obj) {
		if (!(obj instanceof TranspositionPuzzle))
			return false;
		if (obj == this)
			return true;
		return state.equals(((TranspositionPuzzle)obj).state);
	}

	/**
	 * Returns a hash code value for this <code>TranspositionPuzzle</code>, based on
	 * its current configuration.
	 * 
	 * @return A hash code value for this <code>TranspositionPuzzle</code>.
	 */
	public int hashCode() {
		return state.hashCode();
	}
	
	private TranspositionPuzzle swap(int i, int j) {
		StringBuffer sb = new StringBuffer(state);
		sb.setCharAt(i, state.charAt(j));
		sb.setCharAt(j, state.charAt(i));
		return new TranspositionPuzzle(sb.toString());
	}
}
